package 双指针技巧与相关题目;

// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/

public class Code07_FirstMissingPositive {

    // 时间复杂度O(n)，额外空间复杂度O(1)
    public static int firstMissingPositive(int[] nums) {
        // l的左边，都是做到i位置上放着i+1的区域 ，首个断掉的位置l 那缺失的数字就是l+1
        // 永远盯着l位置的数字看，看能不能扩充(l++)
        int l = 0;
        // [r....]垃圾区
        // 最好的状况下，认为 1~r的正整数 是可以收集全的，每个数字收集1个，不能有垃圾
        // 有垃圾呢？预期就会变差(r--)
        int r = nums.length;
        while (l < r){
            // 符合条件
            if(nums[l] == l + 1){
                l++;
            // 垃圾，每出现一次垃圾情况，那么就会交换（l位置的数和 垃圾区r位置的前一个位置的数
            // 交换则垃圾区 r的位置来到 r-1，那么预期要收集的数 1-r 就会变小
            } else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
                swap(nums, l, --r);
            // 即不符合条件，也不是垃圾。进行 l 位置的数和 nums[l] - 1 位置的数交换
            // 即 l位置的数本应该出现在 nums[l] - 1 的位置
            }else {
                swap(nums, l, nums[l] - 1);
            }
        }
        return l + 1;
    }

    public static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
